package 牛客.链表;

import 剑指offer.ListNode;

import java.util.ArrayDeque;
import java.util.Deque;

public class BM11链表相加二 {
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        //链表中数位的顺序从头到尾，和加法的顺序从尾到头相反
        //因此借助栈解决
        Deque<Integer> stack1=new ArrayDeque<>();//官方建议 使用Deque的实现类来代替Stack
        Deque<Integer> stack2=new ArrayDeque<>();

        while (head1!=null) {
            stack1.push(head1.val);
            head1=head1.next;
        }
        while (head2!=null) {
            stack2.push(head2.val);
            head2=head2.next;
        }

        int carry=0;//表示每次的进位
        ListNode ans=null;//表示加和后的节点指向的下一个
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry!=0) {
            int a=stack1.isEmpty() ? 0 : stack1.pop();
            int b=stack2.isEmpty() ? 0 : stack2.pop();

            int cur=a+b+carry;
            carry=cur/10;
            cur %= 10;
            ListNode node=new ListNode(cur);
            node.next=ans;
            ans=node;
        }
        return ans;
    }


    public ListNode addInList1 (ListNode head1, ListNode head2) {
        //反转链表再相加
        ListNode l1=reverse(head1);
        ListNode l2=reverse(head2);

        int carry=0;
        ListNode dummyNode=new ListNode(-1);//傀儡头节点
        while (l1!=null || l2!=null || carry!=0) {
            int a= l1==null?0:l1.val;
            int b= l2==null?0:l2.val;

            int sum=a+b+carry;
            ListNode node=new ListNode(sum%10);
            carry=sum/10;
            node.next=dummyNode.next;
            dummyNode.next=node;

            if (l1!=null) {
                l1=l1.next;
            }
            if (l2!=null) {
                l2=l2.next;
            }

        }

        return dummyNode.next;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev=null;
        ListNode cur=head;
        while (cur!=null) {
            ListNode next=cur.next;
            cur.next=prev;
            prev=cur;
            cur=next;
        }
        return prev;
    }

}
